【题解】 小清新人渣的本愿 莫队+bitset luoguP3674 | Qiuly's blog!

【题解】 小清新人渣的本愿 莫队+bitset luoguP3674

Posted on | Edited on | In | Comments:

莫队 $+$ $bitset$.

我们可以用 $bitset$ 维护当前 $l,r$ 区间数的出现的状态，莫对依旧按照套路搞，然后来考虑怎么回答每一个询问。

对于操做 $1$ ，要求回答我们从当前区间能否找出 $a,b$ 使得其差为 $x$。

很显然，$a-b=x$ 等价于 $a=b+x$。

我们维护的是数的出现的状态，于是可以将当前的 $bitset$ 左移 $x$ 位，也就是让所有数都加上 $x$，然后与原 $bitset$ 做与运算，看看是否有一个 $a$ 出现，如果与的结果非 $0$ ，那么显然是有的，否则没有。

第二个操作有些不好办，我们再开一个 $bitset$ 集，对于一个出现过的数 $i$，在第二个 $bitset$ 集中记为 $N-i$。然后再来看操作要求，这次是让 $a+b=x$。

那么可以得到：

于是设一个数 $z$ ，表示 $N-a$ 。

然后：

移项得：

于是我们将第二个 $bitset$ 右移 $N-x$ 为，显然第二个 $bitset$ 集上的第 $i$ 位代表的就是第一个 $bitset$ 上的 $x-i$ 位。

然后，将两个 $bitset$ 与一下，看看是否同时存在 $a$ 和 $x-a$ 即可。

最后对于第三个操作，貌似bitset也不太好搞，那么直接暴力枚举因子就好了，复杂度 $O(\sqrt{n})$，放心不会炸。具体怎么暴力枚举呢？在 $1 - \sqrt{x}$ 的范围类枚举一个 $j$ ，如果 $x$ % $j==0$ 并且同时存在 $j$ 和 $x/j$，显然就有答案了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cmath>
#include<bitset>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=1e5+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

std::bitset<N> now1,now2; 
int n,m,l,r,s,a[N],c[N],Be[N],ans[N];
struct MO{int opt,l,r,x,id;}q[N];

inline bool cmp(MO a,MO b)
{return Be[a.l]==Be[b.l]?a.r<b.r:a.l<b.l;} 

inline void input(){
    IN(n),IN(m);s=sqrt(n);
    for(int i=1;i<=n;++i)IN(a[i]),Be[i]=(i-1)/s+1;
    for(int i=1;i<=m;++i)
       IN(q[i].opt),IN(q[i].l),IN(q[i].r),IN(q[i].x),q[i].id=i;
    std::sort(q+1,q+1+m,cmp);
    l=1,r=0;now1.reset(),now2.reset();
}

inline void Add(int x){if(c[x]++==0)now1[x]=1,now2[N-x]=1;}
inline void Del(int x){if(--c[x]==0)now1[x]=0,now2[N-x]=0;}

int main(){
    input();
    for(int i=1;i<=m;++i){
        while(l<q[i].l)Del(a[l++]);
        while(l>q[i].l)Add(a[--l]);
        while(r>q[i].r)Del(a[r--]);
        while(r<q[i].r)Add(a[++r]);
        if(q[i].opt==1){
        	if((now1&(now1<<q[i].x)).any())ans[q[i].id]=true;
        }else if(q[i].opt==2){
        	if((now1&(now2>>(N-q[i].x))).any())ans[q[i].id]=true;
        }else if(q[i].opt==3){
        	for(int j=1;j*j<=q[i].x;++j)
        	   if(!(q[i].x%j)&&now1[j]&&now1[q[i].x/j])
        	   {ans[q[i].id]=true;break;}
        }
    }
    for(int i=1;i<=m;++i)
       if(ans[i])printf("hana\n");
       else printf("bi\n"); 
    return 0;
}

本文标题:【题解】 小清新人渣的本愿 莫队+bitset luoguP3674

文章作者:Qiuly

发布时间:2019年02月13日 - 00:00

最后更新:2019年03月29日 - 13:54

原始链接:http://qiulyblog.github.io/2019/02/13/[题解]luoguP3674/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。